home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Memory / BestFitH.cpp next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  38.7 KB  |  1,352 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        BestFitH.cpp
  3.  
  4.     Contains:    BestFitHeap class implementation
  5.  
  6.     Owned by:    Michael Burbidge
  7.  
  8.     Copyright:    © 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.     
  12.          <3>     6/19/96    jpa        1298260: More consistency checks in
  13.                                     CheckSegment
  14.          <2>     1/15/96    TJ        Cleaned Up
  15.         <14>      8/4/95    DM        Leak checking [1267956]
  16.         <13>      5/4/95    jpa        Support for finding largest free block
  17.                                     [1235657] and validating memory ranges
  18.                                     [1246077]. Better calculation of dflt huge
  19.                                     block size [1233941]
  20.         <12>     2/14/95    jpa        Fixed DoIsValidBlock to do proper size
  21.                                     checking (was giving spurious warnings.)
  22.                                     [1215473]
  23.         <11>    12/20/94    jpa        Disallow case where fHugeBlockSize >
  24.                                     sizeIncrement. [1199188]
  25.         <10>     12/5/94    jpa        Nuked errant pragma lib_export's. [1195676]
  26.          <9>    10/24/94    jpa        Don't call CheckTree all over the place
  27.                                     unless gValidate>0.
  28.          <8>     9/29/94    RA        1189812: Mods for 68K build.
  29.          <7>     9/14/94    jpa        Eliminated dependencies on rest of OpenDoc.
  30.                                     Added support for getting the heap of a
  31.                                     block by stuffing heap ptr in busy block
  32.                                     header. [1186692]
  33.          <6>     8/17/94    jpa        Implemented huge-block support [1179565],
  34.                                     segment disposal [1181509] and the
  35.                                     SOM-block flag [1181510].
  36.          <5>      8/8/94    jpa        Added fHugeBlockSize -- not used yet
  37.                                     [1179565]
  38.          <4>      8/2/94    jpa        Install block cushion hooks. Allocate
  39.                                     blocks on 4byte boundaries. Fixed bug when
  40.                                     getting block size (didn't work right with
  41.                                     hooks installed.)
  42.          <3>     6/18/94    MB        Add #pragma lib_export lines
  43.          <2>     6/10/94    MB        Make it build
  44.          <1>      6/9/94    MB        first checked in
  45.          <5>     5/27/94    MB        #1165129: CreateNewSegment doesn't check
  46.                                     for NULL after allocating new segment.
  47.          <4>     5/27/94    MB        #1162181: Fixed MMM integration bug
  48.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  49.          <1>     4/29/94    MB        first checked in
  50.          
  51.     To Do:
  52.     In Progress:
  53.         
  54. */
  55.  
  56. #ifndef _PLATFMEM_
  57. #include "PlatfMem.h"
  58. #endif
  59.  
  60. #ifndef _MEMMGRPV_
  61. #include "MemMgrPv.h"
  62. #endif
  63.  
  64. #ifndef _BESTFITH_
  65. #include "BestFitH.h"
  66. #endif
  67.  
  68. #if MM_DEBUG
  69. #ifndef _MEMHOOKS_
  70. #include "MemHooks.h"
  71. #endif
  72. #endif
  73.  
  74. #ifndef __MEMORY__
  75. #include <Memory.h>
  76. #endif
  77.  
  78. #ifndef __LIMITS__
  79. #include <limits.h>
  80. #endif
  81.  
  82. #ifndef __STRING__
  83. #include <string.h>
  84. #endif
  85.  
  86. #ifndef __STDIO__
  87. #include <stdio.h>
  88. #endif
  89.  
  90.  
  91. #define BLOCKS_ON_4BYTE 1        // Allocate blocks on 4-byte boundaries.
  92.  
  93.  
  94. #if MM_DEBUG
  95. //----------------------------------------------------------------------------------------
  96. // IsValidBlock
  97. //----------------------------------------------------------------------------------------
  98. #pragma segment HeapSeg
  99.  
  100. static const PrivBestFitBlock *ValidBlock(const void* ptr)
  101. {
  102.     if( ptr==kMMNULL )
  103.         return kMMNULL;
  104. #if BLOCKS_ON_4BYTE
  105.     if( (long)ptr & 0x00000003 )
  106.         return kMMNULL;                    // Not on a 4-byte boundary
  107. #endif
  108.         
  109.     const PrivBestFitBlock *blk 
  110.         = (const PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  111.  
  112.     ODBlockSize blkSize = blk->GetSize();
  113.     if( (blkSize >= PrivBestFitBlock::kMinBlockSize || blkSize <= BestFitBlock_kMaxBlockSize)
  114.             && blk->GetBusy()
  115.             && blk->GetMagicNumber() == (unsigned int)PrivBestFitBlock::kMagicNumber )
  116.         return blk;
  117.     else
  118.         return kMMNULL;
  119. }
  120. #endif
  121.  
  122. //========================================================================================
  123. // PrivBestFitBlock
  124. //========================================================================================
  125.  
  126. //----------------------------------------------------------------------------------------
  127. // PrivBestFitBlock::operator >
  128. //----------------------------------------------------------------------------------------
  129. #pragma segment HeapSeg
  130.  
  131. Boolean PrivBestFitBlock::operator>(const PrivBestFitBlock& blk) const
  132. {
  133.     if (GetSize() == blk.GetSize())
  134.         return this > &blk;
  135.     else
  136.         return GetSize() > blk.GetSize();
  137. }
  138.  
  139. //----------------------------------------------------------------------------------------
  140. // PrivBestFitBlock::operator <
  141. //----------------------------------------------------------------------------------------
  142. #pragma segment HeapSeg
  143.  
  144. Boolean PrivBestFitBlock::operator<(const PrivBestFitBlock& blk) const
  145. {
  146.     if (GetSize() == blk.GetSize())
  147.         return this < &blk;
  148.     else
  149.         return GetSize() < blk.GetSize();
  150. }
  151.  
  152. //----------------------------------------------------------------------------------------
  153. // PrivBestFitBlock::operator ==
  154. //----------------------------------------------------------------------------------------
  155. #pragma segment HeapSeg
  156.  
  157. Boolean PrivBestFitBlock::operator==(const PrivBestFitBlock& blk) const
  158. {
  159.     return GetSize() == blk.GetSize() && this == &blk;
  160. }
  161.  
  162. //----------------------------------------------------------------------------------------
  163. // PrivBestFitBlock::StuffAddressAtEnd
  164. //----------------------------------------------------------------------------------------
  165. #pragma segment HeapSeg
  166.  
  167. void PrivBestFitBlock::StuffAddressAtEnd()
  168. {
  169.     // coalescence possible in constant time.
  170.  
  171.     if (!this->GetBusy())
  172.     {
  173.         void** addr= (void**) ((ODBytePtr) this + this->GetSize() - sizeof(PrivBestFitBlock *));
  174.         *addr = this;
  175.     }
  176. #if MM_DEBUG
  177.     else
  178.         MM_WARN("PrivBestFitBlock::StuffAddressAtEnd: corrupt heap!");
  179. #endif
  180. }
  181.  
  182.  
  183. //========================================================================================
  184. // BestFitHeap
  185. //========================================================================================
  186.  
  187. //----------------------------------------------------------------------------------------
  188. // BestFitHeap::BestFitHeap
  189. //----------------------------------------------------------------------------------------
  190. #pragma segment HeapSeg
  191.  
  192. BestFitHeap::BestFitHeap(unsigned long sizeInitial,
  193.                                  unsigned long sizeIncrement,
  194.                                  unsigned long hugeBlockSize,        // "0" means sizeIncrement/2
  195.                                  MMHeapLocation memSrc) :
  196.     MemoryHeap(false, false, false, memSrc)
  197. {
  198. #if MM_DEBUG
  199.     CompilerCheck();
  200. #endif
  201.  
  202.     fSizeIncrement = sizeIncrement;
  203.     fSizeInitial = sizeInitial;
  204.     
  205.     if( hugeBlockSize!=0 )
  206.         fHugeBlockSize = hugeBlockSize;
  207.     else
  208.         fHugeBlockSize = sizeIncrement>>1;
  209.     
  210.     if( fHugeBlockSize > kMaxHugeBlockSize )
  211.         fHugeBlockSize = kMaxHugeBlockSize;
  212.         
  213.     if( fHugeBlockSize > sizeIncrement ) {
  214.         MM_WARN("hugeSize must be <= sizeIncrement");
  215.         fHugeBlockSize = sizeIncrement;        // Cannot allow range between huge size & sizeIncrement
  216.     }
  217.     
  218.     fSegments = NULL;
  219.     
  220. //    this->GrowHeap(fSizeInitial);    * MEB *
  221. }
  222.  
  223. //----------------------------------------------------------------------------------------
  224. // BestFitHeap::~BestFitHeap
  225. //----------------------------------------------------------------------------------------
  226. #pragma segment HeapSeg
  227.  
  228. BestFitHeap::~BestFitHeap()
  229. {
  230.     this->DeleteSegments();
  231. }
  232.  
  233. //----------------------------------------------------------------------------------------
  234. // BestFitHeap::IBestFitHeap    * MEB *
  235. //----------------------------------------------------------------------------------------
  236. #pragma segment HeapSeg
  237.  
  238. void BestFitHeap::IBestFitHeap()
  239. {
  240.     this->GrowHeap(fSizeInitial);
  241.  
  242. #if MM_DEBUG
  243.     ODMemoryHook *hook = new(this->GetLocation()) CBlockStackCrawlHook;
  244.     this->AdoptHook(hook);
  245.     // Block cushion hooks have to be installed before any blocks are allocated
  246.     // in the heap; so do so now if this is a debug build.
  247.     hook = new(this->GetLocation()) CBlockCushionHook;
  248.     this->AdoptHook(hook);
  249. #endif
  250. }
  251.  
  252. //----------------------------------------------------------------------------------------
  253. // BestFitHeap::ExpandHeap    * MEB *
  254. //----------------------------------------------------------------------------------------
  255. #pragma segment HeapSeg
  256.  
  257. void BestFitHeap::ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement)
  258. {
  259.     if (sizeInitial > fSizeInitial)
  260.         fSizeInitial = sizeInitial;
  261.     if (sizeIncrement > fSizeIncrement)
  262.         fSizeIncrement = sizeIncrement;
  263.     
  264.     if (sizeInitial > this->HeapSize())
  265.         this->GrowHeap(sizeInitial);
  266.     else
  267.         this->GrowHeap(sizeIncrement);
  268. }
  269.  
  270. //----------------------------------------------------------------------------------------
  271. // BestFitHeap::BytesFree
  272. //----------------------------------------------------------------------------------------
  273. #pragma segment HeapSeg
  274.  
  275. unsigned long BestFitHeap::BytesFree() const
  276. {
  277.     unsigned long bytesFree, numberOfNodes;
  278.  
  279.     fFreeTree.TreeInfo(bytesFree, numberOfNodes);
  280.     bytesFree -= numberOfNodes * PrivBestFitBlock::kBusyOverhead;
  281.  
  282.     return bytesFree;
  283. }
  284.  
  285. #if MM_DEBUG
  286. //----------------------------------------------------------------------------------------
  287. // BestFitHeap::Check (MM_DEBUG only)
  288. //----------------------------------------------------------------------------------------
  289. #pragma segment HeapSeg
  290.  
  291. void BestFitHeap::Check( HeapWalkProc proc, void *refCon ) const
  292. {
  293.     ODBlockSize blockHeaderSize = this->CallGetHeaderSize();
  294.  
  295.     // ----- validate each segment
  296.     
  297.     PrivBestFitSegment * segment;
  298.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  299.         if( !segment->CheckSegment(proc,refCon,blockHeaderSize) )
  300.             return;
  301.  
  302.     // ----- check the free tree
  303.     
  304.     fFreeTree.CheckTree();
  305. }
  306. #endif
  307.  
  308. #if MM_DEBUG
  309. //----------------------------------------------------------------------------------------
  310. // BestFitHeap::DoFindBlockContaining (MM_DEBUG only)
  311. //----------------------------------------------------------------------------------------
  312. MMBoolean
  313. BestFitHeap::DoFindBlockContaining( const void *start, const void* end,
  314.                                     const void* &blockStart, const void* &blockEnd ) const
  315. {
  316.     PrivBestFitSegment * segment;
  317.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  318.         if( segment->FindBlockContaining(start,end, blockStart,blockEnd) )
  319.             return kMMTrue;
  320.     return kMMFalse;
  321. }
  322. #endif
  323.  
  324. //----------------------------------------------------------------------------------------
  325. // BestFitHeap::DoGetBlockHeap
  326. //----------------------------------------------------------------------------------------
  327. #pragma segment HeapSeg
  328.  
  329. MemoryHeap*
  330. BestFitHeap::DoGetBlockHeap( const void *block ) const
  331. {
  332. #if MM_DEBUG
  333.     if(!ValidBlock(block)) {
  334.         MM_WARN("GetBlockHeap(%p): bogus block",block);
  335.         return kMMNULL;
  336.     }
  337. #endif
  338.     
  339.     PrivBestFitBlock * blk
  340.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  341.  
  342.     BestFitHeap *heap = blk->GetHeap();
  343. #if MM_DEBUG
  344.     if( !heap->ValidateMagicNumber() )
  345.         return kMMNULL;
  346. #endif
  347.     return heap;
  348. }
  349.  
  350. //----------------------------------------------------------------------------------------
  351. // BestFitHeap::DoAllocate
  352. //----------------------------------------------------------------------------------------
  353. #pragma segment HeapSeg
  354.  
  355. void* BestFitHeap::DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize)
  356. {
  357.     ODBlockSize blkSize = size + PrivBestFitBlock::kBusyOverhead;
  358.  
  359.     if (blkSize < PrivBestFitBlock::kMinBlockSize)
  360.         blkSize = PrivBestFitBlock::kMinBlockSize;
  361.  
  362. #if BLOCKS_ON_4BYTE
  363.     // Make sure blkSize is a multiple of 4 (to keep all blocks on 4byte boundaries)
  364.     // (Added this fix on 7/28/94 on Mike's advice. --jpa)
  365.     blkSize = (blkSize+3) & ~0x03L;
  366. #else
  367.     // Make sure blkSize is even
  368.     if (blkSize & 0x01)
  369.         blkSize++;
  370. #endif
  371.  
  372. #if MM_DEBUG
  373.     MM_ASSERT(blkSize <= BestFitBlock_kMaxBlockSize);
  374. #endif
  375.  
  376.     PrivBestFitBlock * blk;
  377.     
  378.     // A "Huge" block is always allocated its own segment, so the memory can be freed
  379.     // to the platform memory manager as soon as the huge block is deleted:
  380.     
  381.     if( size >= fHugeBlockSize ) {
  382.         blk = this->CreateNewSegment(blkSize + PrivBestFitSegment::kSegmentPrefixSize
  383.                                              + sizeof(PrivBestFitBlock) );
  384.         if( blk )
  385.             MM_ASSERT(blk->GetSize()==blkSize);
  386.             
  387.     } else {
  388.         blk = this->SearchFreeBlocks(blkSize);        // Not huge, so search free blocks
  389.         if (blk == NULL && fSizeIncrement > 0)
  390.         {
  391.             this->GrowHeap(fSizeIncrement);            // Make an attempt to expand the heap
  392.             blk = this->SearchFreeBlocks(blkSize);
  393.         }
  394.     }
  395.  
  396.     allocatedSize = 0;
  397.     void* newPtr = NULL;
  398.  
  399.     if (blk != NULL)
  400.     {
  401.         // We found a block, so mark it busy and remove it from the free list.
  402.  
  403.         blk->SetBusy(true);
  404.         this->RemoveFromFreeBlocks(blk);
  405.         blk->SetHeap(this);
  406.         blk->SetIsObject(false);
  407.  
  408.         if (blk->GetSize() - blkSize >= PrivBestFitBlock::kMinBlockSize)
  409.         {
  410.             // The block is big enough to split, so here we do the split.
  411.  
  412.             PrivBestFitBlock *newBlk
  413.                 = new((void *) ((ODBytePtr) blk + blkSize))
  414.                     PrivBestFitBlock(false, true, blk->GetSize() - blkSize);
  415.             this->AddToFreeBlocks(newBlk);
  416.             blk->SetSize(blkSize);
  417.         }
  418.  
  419.         PrivBestFitBlock * nextBlk
  420.             = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  421.         nextBlk->SetPrevBusy(true);
  422.  
  423.         newPtr = (void *) ((ODBytePtr) blk + PrivBestFitBlock::kBusyOverhead);
  424.         allocatedSize = blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  425.     }
  426.  
  427.     return newPtr;
  428. }
  429.  
  430. //----------------------------------------------------------------------------------------
  431. // BestFitHeap::DoBlockSize
  432. //----------------------------------------------------------------------------------------
  433. #pragma segment HeapSeg
  434.  
  435. ODBlockSize BestFitHeap::DoBlockSize(const void* block) const
  436. {
  437.     PrivBestFitBlock * blk
  438.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  439.  
  440. #if MM_DEBUG
  441.     MM_ASSERT(blk->GetBusy());
  442. #endif
  443.     
  444.     return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  445. }
  446.  
  447. //----------------------------------------------------------------------------------------
  448. // BestFitHeap::DoFree
  449. //----------------------------------------------------------------------------------------
  450. #pragma segment HeapSeg
  451.  
  452. void BestFitHeap::DoFree(void* ptr)
  453. {
  454.     PrivBestFitBlock *blk
  455.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  456.  
  457. #if MM_DEBUG
  458.     MM_ASSERT(blk->GetBusy());
  459. #endif
  460.     
  461.     blk->SetBusy(false);
  462.     blk->StuffAddressAtEnd();
  463.  
  464.     PrivBestFitBlock *nextBlk
  465.         = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  466.     nextBlk->SetPrevBusy(false);
  467.  
  468.     if (this->Coalesce(nextBlk))
  469.         this->RemoveFromFreeBlocks(nextBlk);
  470.  
  471.     PrivBestFitBlock * prevBlk = this->Coalesce(blk);
  472.     if (prevBlk)
  473.     {
  474.         this->RemoveFromFreeBlocks(prevBlk);
  475.         //this->AddToFreeBlocks(prevBlk);// Nope, now happens down below unless seg is freed --jpa
  476.         blk = prevBlk;
  477.     }
  478.     
  479.     if( blk->GetIsFirst() ) {
  480.         // If the first block of the segment is free, look just before it for the seg hdr:
  481.         PrivBestFitSegment *segment;
  482.         segment = (PrivBestFitSegment*)( (ODBytePtr)blk - PrivBestFitSegment::kSegmentPrefixSize );
  483. #if MM_DEBUG
  484.         MM_ASSERT(segment->fSegmentSpace==blk);
  485.         MM_ASSERT(blk->GetSize() + sizeof(PrivBestFitBlock) <= segment->fSegmentSize);
  486. #endif
  487.         if( blk->GetSize() + sizeof(PrivBestFitBlock) == segment->fSegmentSize ) {
  488.             this->DeleteSegment(segment);        // Entire seg is free, so delete it
  489.             return;
  490.         }
  491.     }
  492.     
  493.     // If the segment remains, add the free block to the tree:
  494.     this->AddToFreeBlocks(blk);
  495. }
  496.  
  497. //----------------------------------------------------------------------------------------
  498. // BestFitHeap::DoLargestFreeBlock
  499. //----------------------------------------------------------------------------------------
  500. #pragma segment HeapSeg
  501.  
  502. unsigned long BestFitHeap::DoLargestFreeBlock() const
  503. {
  504.     const PrivBestFitBlock *blk = fFreeTree.FindLargestBlock();
  505.     if( blk )
  506.         return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  507.     else
  508.         return 0;
  509. }
  510.  
  511. #if MM_DEBUG
  512. //----------------------------------------------------------------------------------------
  513. // BestFitHeap::DoIsValidBlock
  514. //----------------------------------------------------------------------------------------
  515. #pragma segment HeapSeg
  516.  
  517. Boolean BestFitHeap::DoIsValidBlock(const void* ptr) const
  518. {
  519.     const PrivBestFitBlock *blk = ValidBlock(ptr);
  520.     if( !blk )
  521.         return kMMFalse;
  522.     else
  523.         // Verify that a huge block must be the first block in its segment:
  524.         return blk->GetIsFirst() || blk->GetSize()<fHugeBlockSize;
  525. }
  526. #endif
  527.  
  528. //----------------------------------------------------------------------------------------
  529. // BestFitHeap::DoReset
  530. //----------------------------------------------------------------------------------------
  531. #pragma segment HeapSeg
  532.  
  533. void BestFitHeap::DoReset()
  534. {
  535.     this->DeleteSegments();
  536.     fSegments = NULL;
  537.     fFreeTree = PrivFreeBlockTree();
  538.  
  539.     this->GrowHeap(fSizeInitial);
  540. }
  541.  
  542. //----------------------------------------------------------------------------------------
  543. // BestFitHeap::HeapSize
  544. //----------------------------------------------------------------------------------------
  545. #pragma segment HeapSeg
  546.  
  547. unsigned long BestFitHeap::HeapSize() const
  548. {
  549.     PrivBestFitSegment * segment = fSegments;
  550.     unsigned long heapSize = 0;
  551.  
  552.     while (segment != NULL)
  553.     {
  554.         heapSize += segment->fSegmentSize;
  555.         segment = segment->fNextSegment;
  556.     }
  557.  
  558.     return heapSize;
  559. }
  560.  
  561.  
  562. //----------------------------------------------------------------------------------------
  563. // BestFitHeap::DoSetBlockIsObject
  564. //----------------------------------------------------------------------------------------
  565. void BestFitHeap::DoSetBlockIsObject( void* ptr, Boolean isObject )
  566. {
  567. #if MM_DEBUG
  568.     MM_ASSERT(this->DoIsValidBlock(ptr));
  569. #endif
  570.     PrivBestFitBlock *blk
  571.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  572.     blk->SetIsObject(isObject);
  573. }
  574.  
  575.  
  576.  
  577. //----------------------------------------------------------------------------------------
  578. // BestFitHeap::DoBlockIsObject
  579. //----------------------------------------------------------------------------------------
  580. Boolean BestFitHeap::DoBlockIsObject( const void* ptr ) const
  581. {
  582. #if MM_DEBUG
  583.     MM_ASSERT(this->DoIsValidBlock(ptr));
  584. #endif
  585.     PrivBestFitBlock *blk
  586.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  587.     return blk->GetIsObject();
  588. }
  589.  
  590.  
  591. #if MM_DEBUG
  592. //----------------------------------------------------------------------------------------
  593. // BestFitHeap::IsMyBlock
  594. //----------------------------------------------------------------------------------------
  595. #pragma segment HeapSeg
  596.  
  597. Boolean BestFitHeap::IsMyBlock(const void* blk) const
  598. {
  599.     Boolean myBlock = false;
  600.  
  601.     PrivBestFitSegment * segment = fSegments;
  602.     while (segment != NULL && myBlock == false)
  603.     {
  604.         myBlock = segment->AddressInSegment(blk);
  605.         segment = segment->fNextSegment;
  606.     }
  607.  
  608.     return myBlock;
  609. }
  610. #endif
  611.  
  612. #if MM_DEBUG
  613. //----------------------------------------------------------------------------------------
  614. // BestFitHeap::Print
  615. //----------------------------------------------------------------------------------------
  616. #pragma segment HeapSeg
  617.  
  618. void BestFitHeap::Print(char* msg) const
  619. {
  620.     MM_PRINT("********** BestFitHeap **********\n");
  621.     fFreeTree.PrintTree();
  622.     MM_PRINT("\n");
  623. }
  624. #endif
  625.  
  626. //----------------------------------------------------------------------------------------
  627. // BestFitHeap::AddToFreeBlocks
  628. //----------------------------------------------------------------------------------------
  629. #pragma segment HeapSeg
  630.  
  631. void BestFitHeap::AddToFreeBlocks(PrivBestFitBlock* blk)
  632. {
  633.     fFreeTree.AddBlock(blk);
  634. }
  635.  
  636. //----------------------------------------------------------------------------------------
  637. // BestFitHeap::Coalesce: Coalesce blk with the previous block if both are free.
  638. //----------------------------------------------------------------------------------------
  639. #pragma segment HeapSeg
  640.  
  641. PrivBestFitBlock* BestFitHeap::Coalesce(PrivBestFitBlock* blk)
  642. {
  643.     PrivBestFitBlock * prevBlk = NULL;
  644.  
  645.     if (!blk->GetBusy() && !blk->GetPreviousBusy())
  646.     {
  647. #if MM_DEBUG
  648.         if (blk->GetSize() < PrivBestFitBlock::kMinBlockSize)
  649.             MM_WARN("BestFitHeap::Coalesce: corrupt heap!");
  650. #endif
  651.             
  652.         prevBlk = *(PrivBestFitBlock **) ((ODBytePtr) blk - sizeof(ODBlockSize));
  653.         prevBlk->SetSize(prevBlk->GetSize() + blk->GetSize());
  654.         prevBlk->StuffAddressAtEnd();
  655.     }
  656.  
  657.     return prevBlk;
  658. }
  659.  
  660. //----------------------------------------------------------------------------------------
  661. // BestFitHeap::CreateNewSegment
  662. //----------------------------------------------------------------------------------------
  663. #pragma segment HeapSeg
  664.  
  665. PrivBestFitBlock* BestFitHeap::CreateNewSegment(unsigned long size)
  666. {
  667. #ifdef BUILD_WIN16
  668.     MM_ASSERT(size < 64L * 1024L);
  669. #endif
  670.  
  671. #if BLOCKS_ON_4BYTE
  672.     // Make sure size is a multiple of 4 (to keep all blocks on 4byte boundaries)
  673.     // (Added this fix on 7/28/94 on Mike's advice. --jpa)
  674.     size = (size+3) & ~0x03L;
  675.     // For this to work, kSegmentPrefixSize and kSegmentSuffixSize must also be
  676.     // multiples of 4.
  677. #else
  678.     // Make sure segment size is even
  679.     if (size & 0x01)
  680.         size++;
  681. #endif
  682.  
  683.     Boolean disposable = (fSegments!=NULL);        // First segment is NOT disposable
  684.  
  685.     PrivBestFitSegment * segment
  686.         = (PrivBestFitSegment *)this->AllocateRawMemory((ODBlockSize) size);
  687.  
  688.     if (segment == NULL)
  689.         return NULL;
  690.     else {
  691.         // The actual usable space is offset by the size of the fields
  692.         // of a PrivBestFitSegment.
  693.     
  694.         segment->fSegmentSpace 
  695.             = (void *) ((ODBytePtr) segment + PrivBestFitSegment::kSegmentPrefixSize);
  696.         segment->fSegmentSize = size - PrivBestFitSegment::kSegmentPrefixSize;
  697.     
  698.         // Add the segment to the list of segments in this heap.
  699.     
  700.         segment->fNextSegment = fSegments;
  701.         fSegments = segment;
  702.     
  703.         // Suffix the segment with a busy block of zero length so that the last free
  704.         // block is not coalesced with a block past the fEnd of the segment.
  705.     
  706.         void * endOfSegment 
  707.             = (void *) ((ODBytePtr) segment->fSegmentSpace + segment->fSegmentSize);
  708.         PrivBestFitBlock *blk
  709.             = new((void *) ((ODBytePtr) endOfSegment - sizeof(PrivBestFitBlock)))
  710.                 PrivBestFitBlock(true, false, sizeof(PrivBestFitBlock));
  711.         blk->SetHeap(this);
  712.     
  713.         // Create one free block out of this entire segment and Add it to the
  714.         // free block list.
  715.     
  716.         blk = new(segment->fSegmentSpace)PrivBestFitBlock(false, true, segment->fSegmentSize - sizeof(PrivBestFitBlock));
  717.     
  718.         if( disposable )
  719.             // This is the 1st block (positionally) in the heap, so set its bit:  --jpa
  720.             blk->SetIsFirst(true); 
  721.         
  722.         this->AddToFreeBlocks(blk);
  723.         
  724.         return blk;
  725.     }
  726. }
  727.  
  728. //----------------------------------------------------------------------------------------
  729. // BestFitHeap::DeleteSegment
  730. //----------------------------------------------------------------------------------------
  731. #pragma segment HeapSeg
  732.  
  733. void BestFitHeap::DeleteSegment( PrivBestFitSegment *seg )
  734. {
  735.     // The segment MUST be empty, and its single free block
  736.     // must already have been removed from the free block tree.  --jpa
  737.     
  738.     PrivBestFitSegment *segment = fSegments;
  739.     
  740.     if( segment == seg ) {
  741.         fSegments = seg->fNextSegment;
  742.         this->FreeRawMemory(seg);
  743.         return;
  744.         
  745.     } else
  746.         while (segment != NULL)
  747.             if( segment->fNextSegment == seg ) {
  748.                 segment->fNextSegment = seg->fNextSegment;
  749.                 this->FreeRawMemory(seg);
  750.                 return;
  751.             } else
  752.                 segment = segment->fNextSegment;
  753.  
  754.     MM_WARN("Segment not found in list!");
  755. }
  756.  
  757. //----------------------------------------------------------------------------------------
  758. // BestFitHeap::DeleteSegments
  759. //----------------------------------------------------------------------------------------
  760. #pragma segment HeapSeg
  761.  
  762. void BestFitHeap::DeleteSegments()
  763. {
  764.     PrivBestFitSegment * segment = fSegments;
  765.     while (segment != NULL)
  766.     {
  767.         PrivBestFitSegment * nextSegment = segment->fNextSegment;
  768.         this->FreeRawMemory(segment);
  769.         segment = nextSegment;
  770.     }
  771. }
  772.  
  773. //----------------------------------------------------------------------------------------
  774. // BestFitHeap::GrowHeap
  775. //----------------------------------------------------------------------------------------
  776. #pragma segment HeapSeg
  777.  
  778. void BestFitHeap::GrowHeap(unsigned long sizeIncrement)
  779. {
  780. #ifdef BUILD_WIN16
  781.     // To avoid crossing 64K boundries on pointer arithmatic, the size of each segment
  782.     // must be limited to 64K. So a single grow request may result in more than one
  783.     // segment being allocated.
  784.     
  785.     const unsigned long kSegmentSizeLimit = 1024L * 62L;     // Allow for 2K overhead
  786.     
  787.     while (sizeIncrement > 0)
  788.     {
  789.         unsigned long segmentSize = sizeIncrement;
  790.         if (segmentSize > kSegmentSizeLimit)
  791.             segmentSize = kSegmentSizeLimit;
  792.         this->CreateNewSegment(segmentSize);
  793.         sizeIncrement -= segmentSize;
  794.     }
  795. #else
  796.     this->CreateNewSegment(sizeIncrement);
  797. #endif
  798. }
  799.  
  800. //----------------------------------------------------------------------------------------
  801. // BestFitHeap::RemoveFromFreeBlocks
  802. //----------------------------------------------------------------------------------------
  803. #pragma segment HeapSeg
  804.  
  805. void BestFitHeap::RemoveFromFreeBlocks(PrivBestFitBlock* blk)
  806. {
  807.     fFreeTree.RemoveBlock(blk);
  808. }
  809.  
  810. //----------------------------------------------------------------------------------------
  811. // BestFitHeap::SearchFreeBlocks
  812. //----------------------------------------------------------------------------------------
  813. #pragma segment HeapSeg
  814.  
  815. PrivBestFitBlock* BestFitHeap::SearchFreeBlocks(ODBlockSize size)
  816. {
  817.     //all blocks are of even length, so round up to fNext even number
  818.  
  819.     if (size & 1)
  820.         size++;
  821.  
  822.     return fFreeTree.SearchForBlock(size, NULL, NULL);
  823. }
  824.  
  825. #if MM_DEBUG
  826. //----------------------------------------------------------------------------------------
  827. // BestFitHeap::CompilerCheck
  828. //----------------------------------------------------------------------------------------
  829. #pragma segment HeapSeg
  830.  
  831. void BestFitHeap::CompilerCheck()
  832. {
  833.     MemoryHeap::CompilerCheck();
  834.     
  835.     char buffer[sizeof(PrivBestFitBlock) + sizeof(void *)];
  836.     PrivBestFitBlock &block = *((PrivBestFitBlock *) buffer);
  837.         
  838.     // Check to make sure the bit field setters and getters work.
  839.     
  840.     block.SetBlockType(3);
  841.     block.SetBusy(true);
  842.     block.SetPrevBusy(false);
  843. #ifndef BUILD_WIN16
  844.     block.SetSize(100201);
  845. #endif
  846.     block.SetMagicNumber(3);
  847.  
  848.     MM_ASSERT(block.GetBlockType() == 3);
  849.     MM_ASSERT(block.GetBusy() == true);
  850.     MM_ASSERT(block.GetPreviousBusy() == false);
  851. #ifndef BUILD_WIN16
  852.     MM_ASSERT(block.GetSize() == 100201);
  853. #endif
  854.     MM_ASSERT(block.GetMagicNumber() == 3);
  855.     
  856.     block.SetBlockType(2);
  857.     block.SetBusy(false);
  858.     block.SetPrevBusy(true);
  859.     block.SetSize(150);
  860.     block.SetMagicNumber(2);
  861.  
  862.     MM_ASSERT(block.GetBlockType() == 2);
  863.     MM_ASSERT(block.GetBusy() == false);
  864.     MM_ASSERT(block.GetPreviousBusy() == true);
  865.     MM_ASSERT(block.GetSize() == 150);
  866.     MM_ASSERT(block.GetMagicNumber() == 2);
  867. }
  868. #endif
  869.  
  870.  
  871. //========================================================================================
  872. // CLASS PrivFreeBlockTree
  873. //========================================================================================
  874.  
  875. //----------------------------------------------------------------------------------------
  876. // PrivBestFitSegment::CheckSegment
  877. //----------------------------------------------------------------------------------------
  878.  
  879. Boolean PrivBestFitSegment::CheckSegment( HeapWalkProc proc, void *refCon, ODBlockSize hdrSize )
  880. {
  881.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  882.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  883.     unsigned long blksScanned = 0;
  884.  
  885.     // ----- spin through all the blocks in segment do some consistency checks
  886.     
  887.     while (blk < segmentEnd)
  888.     {
  889.         PrivBestFitBlock *nextBlk;
  890.         MM_ASSERT(blk->GetMagicNumber() == PrivBestFitBlock::kMagicNumber);
  891.         MM_ASSERT(blk->GetBlockType() == PrivBestFitBlock::kBlockTypeId);
  892.         nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  893.         if(nextBlk==blk) {
  894.             MM_WARN("Block %p header damaged -- skipping segment",blk);
  895.             return false;
  896.         } else if( nextBlk > segmentEnd ) {
  897.             MM_WARN("Block %p unnaturally large -- skipping segment",blk);
  898.             return false;
  899.         } else if (nextBlk < segmentEnd)
  900.             MM_ASSERT(nextBlk->GetPreviousBusy() == blk->GetBusy());
  901.         
  902.         if( proc )            // Call user proc if they supplied one
  903.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  904.                 ODBytePtr userBlk = (ODBytePtr)blk + PrivBestFitBlock::kBusyOverhead + hdrSize;
  905.                 if( (*proc)((void*)userBlk, blk->GetSize()-hdrSize, blk->GetIsObject(), refCon) == false )
  906.                     return false;        // proc can return false to abort
  907.             }
  908.         
  909.         blksScanned++;
  910.         blk = nextBlk;
  911.     }
  912.  
  913.     // ----- if sizes are valid we should be exactly at the end of the segment
  914.     
  915.     MM_ASSERT(blk == segmentEnd);
  916.     return true;
  917. }
  918.  
  919. #if MM_DEBUG
  920. //----------------------------------------------------------------------------------------
  921. // PrivBestFitSegment::FindBlockContaining
  922. //----------------------------------------------------------------------------------------
  923.  
  924. MMBoolean
  925. PrivBestFitSegment::FindBlockContaining( const void *start, const void* end,
  926.                                          const void* &blockStart, const void* &blockEnd ) const
  927. {
  928.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  929.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  930.     
  931.     if( end<=blk || start>=segmentEnd )
  932.         return kMMFalse;
  933.     else {
  934.         // Memory range intersects range of this segment:
  935.         while (blk < segmentEnd)
  936.         {
  937.             blockStart = blockEnd = NULL;
  938.             PrivBestFitBlock *nextBlk;
  939.             nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  940.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  941.                 if( start <= nextBlk ) {
  942.                     // The memory range starts before the next block, so return:
  943.                     blockStart = (char*)blk + PrivBestFitBlock::kBusyOverhead;
  944.                     blockEnd   = nextBlk;
  945.                     break;
  946.                 }
  947.             }
  948.             blk = nextBlk;
  949.         }
  950.         return kMMTrue;
  951.     }
  952. }
  953.  
  954. #endif
  955.  
  956.  
  957. //========================================================================================
  958. // CLASS PrivFreeBlockTree
  959. //========================================================================================
  960.  
  961. //----------------------------------------------------------------------------------------
  962. // PrivFreeBlockTree::PrivFreeBlockTree
  963. //----------------------------------------------------------------------------------------
  964. #pragma segment HeapSeg
  965.  
  966. PrivFreeBlockTree::PrivFreeBlockTree() :
  967.     fRoot(true, true, 0)
  968. {
  969.     fRoot.SetRight(NULL);
  970.     fRoot.SetLeft(NULL);
  971. }
  972.  
  973. //----------------------------------------------------------------------------------------
  974. // PrivFreeBlockTree::PrivFreeBlockTree
  975. //----------------------------------------------------------------------------------------
  976. #pragma segment HeapSeg
  977.  
  978. PrivFreeBlockTree::PrivFreeBlockTree(const PrivFreeBlockTree& blk) :
  979.     fRoot(blk.fRoot)
  980. {
  981. }
  982.  
  983. //----------------------------------------------------------------------------------------
  984. // PrivFreeBlockTree::operator=
  985. //----------------------------------------------------------------------------------------
  986. #pragma segment HeapSeg
  987.  
  988. PrivFreeBlockTree& PrivFreeBlockTree::operator=(const PrivFreeBlockTree& blk)
  989. {
  990.     fRoot = blk.fRoot;
  991.     return (*this);
  992. }
  993.  
  994. //----------------------------------------------------------------------------------------
  995. // PrivFreeBlockTree::AddBlock
  996. //----------------------------------------------------------------------------------------
  997. #pragma segment HeapSeg
  998.  
  999. void PrivFreeBlockTree::AddBlock(PrivBestFitBlock* blk)
  1000. {    
  1001. #if MM_DEBUG
  1002.     if( gValidate>0 )
  1003.         this->CheckTree();
  1004.  
  1005. #ifdef OD_INTENSE_DEBUG
  1006.     MM_PRINT("PrivFreeBlockTree::AddBlock Entry-------------------------------------\n");
  1007.     this->PrintTree();
  1008. #endif
  1009. #endif
  1010.  
  1011.     PrivBestFitBlock * parent;
  1012.  
  1013.     this->SearchForBlock(blk->GetSize(), blk, &parent);
  1014.  
  1015.     blk->SetRight(NULL);
  1016.     blk->SetLeft(NULL);
  1017.     blk->SetParent(parent);
  1018.  
  1019.     if (*blk > *parent)
  1020.         parent->SetRight(blk);
  1021.     else
  1022.         parent->SetLeft(blk);
  1023.  
  1024. #if MM_DEBUG
  1025.     if( gValidate>0 )
  1026.         this->CheckTree();
  1027.  
  1028. #ifdef OD_INTENSE_DEBUG
  1029.     MM_PRINT("PrivFreeBlockTree::AddBlock Exit\n");
  1030.     this->PrintTree();
  1031.     MM_PRINT("\n");
  1032. #endif
  1033. #endif
  1034. }
  1035.  
  1036. #if MM_DEBUG
  1037. //----------------------------------------------------------------------------------------
  1038. // PrivFreeBlockTree::CheckTree
  1039. //----------------------------------------------------------------------------------------
  1040. #pragma segment HeapSeg
  1041.  
  1042. void PrivFreeBlockTree::CheckTree() const
  1043. {
  1044.     this->CheckTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1045. }
  1046. #endif
  1047.  
  1048. #if MM_DEBUG
  1049. //----------------------------------------------------------------------------------------
  1050. // PrivFreeBlockTree::PrintTree
  1051. //----------------------------------------------------------------------------------------
  1052. #pragma segment HeapSeg
  1053.  
  1054. void PrivFreeBlockTree::PrintTree() const
  1055. {
  1056.     this->PrintTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1057. }
  1058. #endif
  1059.  
  1060. //----------------------------------------------------------------------------------------
  1061. // PrivFreeBlockTree::RemoveBlock
  1062. //----------------------------------------------------------------------------------------
  1063. #pragma segment HeapSeg
  1064.  
  1065. void PrivFreeBlockTree::RemoveBlock(PrivBestFitBlock* blk)
  1066. {
  1067. #if MM_DEBUG
  1068.     if( gValidate > 0 )
  1069.         this->CheckTree();
  1070.  
  1071. #ifdef OD_INTENSE_DEBUG
  1072.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Entry----------------------------------\n");
  1073.     this->PrintTree();
  1074. #endif
  1075. #endif
  1076.  
  1077.     PrivBestFitBlock * spliceOutBlk;
  1078.  
  1079.     // Decide which block to splice out of the tree. Either the block being
  1080.     // removed, or its successor block in the tree.
  1081.  
  1082.     if (blk->GetLeft() == NULL || blk->GetRight() == NULL)
  1083.         spliceOutBlk = blk;
  1084.     else
  1085.         spliceOutBlk = this->GetSuccessorBlk(blk);
  1086.  
  1087.     // Splice the node out of the tree
  1088.  
  1089.     PrivBestFitBlock * tmp;
  1090.     PrivBestFitBlock * parent = spliceOutBlk->GetParent();
  1091.     if (spliceOutBlk->GetLeft())
  1092.         tmp = spliceOutBlk->GetLeft();
  1093.     else
  1094.         tmp = spliceOutBlk->GetRight();
  1095.     if (tmp)
  1096.         tmp->SetParent(parent);
  1097.     if (spliceOutBlk == parent->GetLeft())
  1098.         parent->SetLeft(tmp);
  1099.     else
  1100.         parent->SetRight(tmp);
  1101.  
  1102.     // If we spliced out the successor to blk above then we need to patch the successor
  1103.     // back in, in Place of blk.
  1104.  
  1105.     if (spliceOutBlk != blk)
  1106.     {
  1107.         PrivBestFitBlock * parent = blk->GetParent();
  1108.  
  1109.         // Fix up the parent's child pointer.
  1110.  
  1111.         if (parent->GetLeft() == blk)
  1112.             parent->SetLeft(spliceOutBlk);
  1113.         else
  1114.             parent->SetRight(spliceOutBlk);
  1115.  
  1116.         // Fix up the splice in block's pointers.
  1117.  
  1118.         spliceOutBlk->SetParent(parent);
  1119.         spliceOutBlk->SetLeft(blk->GetLeft());
  1120.         spliceOutBlk->SetRight(blk->GetRight());
  1121.  
  1122.         // Fix up the children of the splice in block's parent pointers.
  1123.  
  1124.         if (spliceOutBlk->GetLeft())
  1125.             (spliceOutBlk->GetLeft())->SetParent(spliceOutBlk);
  1126.         if (spliceOutBlk->GetRight())
  1127.             (spliceOutBlk->GetRight())->SetParent(spliceOutBlk);
  1128.     }
  1129.  
  1130. #if MM_DEBUG
  1131.     if( gValidate>0 )
  1132.         this->CheckTree();
  1133.  
  1134. #ifdef OD_INTENSE_DEBUG
  1135.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Exit\n");
  1136.     this->PrintTree();
  1137.     MM_PRINT("\n");
  1138. #endif
  1139. #endif
  1140. }
  1141.  
  1142. //----------------------------------------------------------------------------------------
  1143. // PrivFreeBlockTree::SearchForBlock
  1144. //----------------------------------------------------------------------------------------
  1145. #pragma segment HeapSeg
  1146.  
  1147. PrivBestFitBlock* PrivFreeBlockTree::SearchForBlock(ODBlockSize size,
  1148.                                             void* blk,
  1149.                                             PrivBestFitBlock** insertLeaf)
  1150. {
  1151. #if MM_DEBUG
  1152.     if( gValidate>0 )
  1153.         this->CheckTree();
  1154.  
  1155. #ifdef OD_INTENSE_DEBUG
  1156.     char str[80];
  1157.     sprintf(str, "PrivFreeBlockTree::SearchForBlock(%d)---------------------------------\n", size);
  1158.     MM_PRINT(str);
  1159.     this->PrintTree();
  1160. #endif
  1161. #endif
  1162.  
  1163.     long minDiff = LONG_MAX;
  1164.     PrivBestFitBlock * minDiffBlock = NULL;
  1165.     PrivBestFitBlock * currentBlock = &fRoot;
  1166.     do
  1167.     {
  1168.         long diff = currentBlock->GetSize() - size;
  1169.         if (diff >= 0 && diff < minDiff)
  1170.         {
  1171.             minDiffBlock = currentBlock;
  1172.             minDiff = diff;
  1173.         }
  1174.  
  1175.         if (insertLeaf)
  1176.             *insertLeaf = currentBlock;
  1177.  
  1178.         // Determine which branch of the tree to continue down. Since duplicate keys are
  1179.         // difficult to deal with in binary trees, we use the address of blocks to break
  1180.         // ties, in the case of two blocks whose size are equal.
  1181.  
  1182.         if (size < currentBlock->GetSize())
  1183.             currentBlock = currentBlock->GetLeft();
  1184.         else if (size > currentBlock->GetSize())
  1185.             currentBlock = currentBlock->GetRight();
  1186.         else if (blk)
  1187.         {
  1188.             if (blk <= currentBlock)
  1189.                 currentBlock = currentBlock->GetLeft();
  1190.             else
  1191.                 currentBlock = currentBlock->GetRight();
  1192.         }
  1193.         else
  1194.             currentBlock = currentBlock->GetLeft();
  1195.  
  1196.     } while (currentBlock != NULL);
  1197.  
  1198.     return minDiffBlock;
  1199. }
  1200.  
  1201. //----------------------------------------------------------------------------------------
  1202. // PrivFreeBlockTree::FindLargestBlock
  1203. //----------------------------------------------------------------------------------------
  1204. #pragma segment HeapSeg
  1205.  
  1206. const PrivBestFitBlock* PrivFreeBlockTree::FindLargestBlock( ) const
  1207. {
  1208.     // The block to the right in the tree is always larger...
  1209.     
  1210.     const PrivBestFitBlock * currentBlock = &fRoot;
  1211.     const PrivBestFitBlock * nextBlock;
  1212.     while( (nextBlock = currentBlock->GetRight()) != kMMNULL )
  1213.         currentBlock = nextBlock;
  1214.     return currentBlock;
  1215. }
  1216.  
  1217. //----------------------------------------------------------------------------------------
  1218. // PrivFreeBlockTree::TreeInfo
  1219. //----------------------------------------------------------------------------------------
  1220. #pragma segment HeapSeg
  1221.  
  1222. void PrivFreeBlockTree::TreeInfo(unsigned long& bytesFree,
  1223.                              unsigned long& numberOfNodes) const
  1224. {
  1225.     bytesFree = numberOfNodes = 0;
  1226.     this->TreeInfoHelper(&((PrivFreeBlockTree *)this)->fRoot, bytesFree, numberOfNodes);
  1227.  
  1228.     // Subtract one from the number of nodes to account for the header node which
  1229.     // is always empty.
  1230.  
  1231.     numberOfNodes--;
  1232. }
  1233.  
  1234. #if MM_DEBUG
  1235. //----------------------------------------------------------------------------------------
  1236. // PrivFreeBlockTree::CheckTreeHelper
  1237. //----------------------------------------------------------------------------------------
  1238. #pragma segment HeapSeg
  1239.  
  1240. void PrivFreeBlockTree::CheckTreeHelper(PrivBestFitBlock* blk) const
  1241. {
  1242.     if (blk == NULL)
  1243.         return;
  1244.  
  1245.     this->CheckTreeHelper(blk->GetLeft());
  1246.  
  1247.     PrivBestFitBlock * parent = blk->GetParent();
  1248.     if (parent != NULL)
  1249.     {
  1250.         if (parent->GetRight() == blk)
  1251.         {
  1252.             if (*blk < *parent)
  1253.             {
  1254.                 this->PrintTree();
  1255.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1256.                                              "Corrupt free list tree: "
  1257.                                              "right child less than parent.");
  1258.             }
  1259.         }
  1260.         else if (parent->GetLeft() == blk)
  1261.         {
  1262.             if (*blk > *parent)
  1263.             {
  1264.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1265.                                              "Corrupt free list tree: "
  1266.                                              "left child greater than parent.");
  1267.             }
  1268.         }
  1269.         else
  1270.         {
  1271.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1272.                                              "Corrupt free list tree: "
  1273.                                              "I am not my parent's child.");
  1274.         }
  1275.     }
  1276. }
  1277. #endif
  1278.  
  1279. //----------------------------------------------------------------------------------------
  1280. // PrivFreeBlockTree::GetSuccessorBlk
  1281. //----------------------------------------------------------------------------------------
  1282. #pragma segment HeapSeg
  1283.  
  1284. PrivBestFitBlock* PrivFreeBlockTree::GetSuccessorBlk(PrivBestFitBlock* blk)
  1285. {
  1286.     if (blk->GetRight())
  1287.     {
  1288.         PrivBestFitBlock * current = blk->GetRight();
  1289.         while (current->GetLeft())
  1290.             current = current->GetLeft();
  1291.         return current;
  1292.     }
  1293.     else
  1294.     {
  1295.         PrivBestFitBlock * parent = blk->GetParent();
  1296.         PrivBestFitBlock * current = NULL;
  1297.         while (parent != NULL && current == parent->GetRight())
  1298.         {
  1299.             current = parent;
  1300.             parent = parent->GetParent();
  1301.         }
  1302.         return parent;
  1303.     }
  1304. }
  1305.  
  1306. #if MM_DEBUG
  1307. //----------------------------------------------------------------------------------------
  1308. // PrivFreeBlockTree::PrintTreeHelper
  1309. //----------------------------------------------------------------------------------------
  1310. #pragma segment HeapSeg
  1311.  
  1312. void PrivFreeBlockTree::PrintTreeHelper(PrivBestFitBlock* blk,
  1313.                                         int level) const
  1314. {
  1315.     for (int i = 0; i < level; i++)
  1316.         MM_PRINT("\t");
  1317.  
  1318.     if (blk == NULL)
  1319.     {
  1320.         MM_PRINT("NULL\n");
  1321.         return;
  1322.     }
  1323.  
  1324.     char str[80];
  1325.     //sprintf(str, "Block=%lx fSize=%ld\n", blk, blk->GetSize());
  1326.     MM_PRINT(str);
  1327.  
  1328.     this->PrintTreeHelper(blk->GetLeft(), level + 1);
  1329.     this->PrintTreeHelper(blk->GetRight(), level + 1);
  1330. }
  1331. #endif
  1332.  
  1333. //----------------------------------------------------------------------------------------
  1334. // PrivFreeBlockTree::TreeInfoHelper
  1335. //----------------------------------------------------------------------------------------
  1336. #pragma segment HeapSeg
  1337.  
  1338. void PrivFreeBlockTree::TreeInfoHelper(PrivBestFitBlock* blk,
  1339.                                        unsigned long& bytesFree,
  1340.                                        unsigned long& numberOfNodes) const
  1341. {
  1342.     if (blk == NULL)
  1343.         return;
  1344.  
  1345.     this->TreeInfoHelper(blk->GetLeft(), bytesFree, numberOfNodes);
  1346.  
  1347.     numberOfNodes++;
  1348.     bytesFree += blk->GetSize();
  1349.  
  1350.     this->TreeInfoHelper(blk->GetRight(), bytesFree, numberOfNodes);
  1351. }
  1352.